package leetcode_day._2021._202111;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/5 20:28
 * 最长定差子序列
 * 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，
 * 该子序列中相邻元素之间的差等于 difference 。
 * 算法：哈希表  动态规划
 */
public class _05_1218 {

    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> map = new HashMap<>(16);
        for (int i : arr) map.put(i, map.getOrDefault(i - difference, 0) + 1);
        int ans = Integer.MIN_VALUE;
        for (Integer value : map.values()) ans = Math.max(ans, value);
        return ans;
    }

}
